/**
分析:

字符串 target 的字序列可以理解成位字每是否显示，如
abc 全显示，即为111
其子序 ab 即为 110
ac: 101
bc: 011
a: 100
b: 010
c: 001

*/

/**
 * @param {string[]} stickers
 * @param {string} target
 * @return {number}
 */
export var minStickers = function (stickers, target) {
  const m = target.length
  // target 的子序列有 2^m 个 （每位字符有出现和不出现的两种可能性）
  // memo用于记录每个子序列的最小结果
  const memo = new Array(1 << m).fill(-1)
  // memo[0] 为终点，即使有位都变成0。
  memo[0] = 0
  // 初轮target全部字母都出现 abc: 111, 即 1 << m -1
  const res = dp(stickers, target, memo, (1 << m) - 1)
  return res <= m ? res : -1
}

const dp = (stickers, target, memo, mask) => {
  const m = target.length
  if (memo[mask] < 0) {
    // 因为次数不可能大于target长度，所以以m+1使为初始值于计算出来的值作为比较
    let res = m + 1
    // 遍历stickers, 计算sticker与mask的最大交集,
    // 剩下的为left, 有交集即left < mask, 说明此sticker使用了一次。
    for (const sticker of stickers) {
      // left 为没有交集的部分
      let left = mask
      // 记录各sticker每个子母出现次数
      const cnt = new Array(26).fill(0)
      for (let i = 0; i < sticker.length; i++) {
        cnt[sticker[i].charCodeAt() - 'a'.charCodeAt()]++
      }
      // 判断target中每个字母是否出现在sticker中
      for (let i = 0; i < target.length; i++) {
        const c = target[i]
        if (((mask >> i) & 1) === 1 && cnt[c.charCodeAt() - 'a'.charCodeAt()] > 0) {
          cnt[c.charCodeAt() - 'a'.charCodeAt()]--
          // 把该位字母设为不显示
          // left = 111, i = 1;  '111' ^ 1 << 1 -> '101'
          // left = 101, i = 2;  '101' ^ 1 << 2 -> '001'
          left ^= 1 << i
        }
      }
      // 乘下的left作为新的mask进行相重的逻辑处理
      // [动态划规，当前mask的结果为前推一个mark(即left)的结果加1)]
      if (left < mask) {
        res = Math.min(res, dp(stickers, target, memo, left) + 1)
      }
    }
    memo[mask] = res
  }
  return memo[mask]
}
